#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <cstdio>
#include <climits>
#include <algorithm>

class Solution1
{
public:
    void hanota(std::vector<int>& A, std::vector<int>& B, std::vector<int>& C) 
    {
        return dfs(A, B, C, A.size());    
    }

    void dfs(std::vector<int>& x, std::vector<int>& y, std::vector<int>& z, int nums)
    {
        // 退出条件
        if(nums == 1) {
            z.emplace_back(x.back());
            x.pop_back();
            return;
        }

        // 函数体
        // 1.将x上的n-1个盘子通过z，放在y上
        dfs(x, z, y, nums - 1);

        // 2.将x上的最底下的盘子放到z上
        z.emplace_back(x.back());
        x.pop_back();

        // 3.将y上的盘子借助x，放到z上
        dfs(y, x, z, nums - 1);
    }
};

struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution2
{
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) 
    {
        return dfs(list1, list2);
    }
    ListNode* dfs(ListNode* l1, ListNode* l2)
    {
        if(l1 == nullptr || l2 == nullptr)
            return l1 == nullptr ? l2 : l1;
        if(l1->val <= l2->val) {
            l1->next = dfs(l1->next, l2);
        }else{
            l2->next = dfs(l1, l2->next);
        }
        return l1->val <= l2->val ? l1 : l2;
    }
};

// 反转链表
class Solution3 
{
public:
    ListNode* reverseList_recursion(ListNode* head) 
    {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* newhead = reverseList_recursion(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newhead;
    }
    ListNode* reverseList(ListNode* head) 
    {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode *newHead = new ListNode(0);
        while(head) {
            ListNode* Next = head->next;
            head->next = newHead->next;
            newHead->next = head;
            head = Next;
        }
        return newHead->next;
    }
};

// 两两交换链表中的节点
class Solution4 
{
public:
    ListNode* swapPairs_recursion(ListNode* head) 
    {
        if(head == nullptr || head->next == nullptr) return head;
        ListNode* newHead = head->next;
        head->next = swapPairs_recursion(head->next->next);
        newHead->next = head;
        return newHead;
    }

    ListNode* swapPairs_iteration(ListNode* head) 
    {
        if(!head || !head->next) return head;
        ListNode *virtualHead = new ListNode;
        virtualHead->next = head;
        ListNode *cur = head;
        ListNode *prev = virtualHead;
        ListNode *next = cur->next;
        ListNode *nnext = next->next;

        while(cur && next) {
            prev->next = next;
            next->next = cur;
            cur->next = nnext;

            prev = cur;
            cur = nnext;
            if(cur) next = cur->next;
            if(next) nnext = next->next;
        }
        cur = virtualHead->next;
        delete virtualHead;
        return cur;
    }
};

// 快速幂
class Solution5
{
public:
    double myPow(double x, int n) 
    {
        return n < 0 ? 1.0 / pow1(x, -(long long)n) : pow1(x, n); 
    }

    double pow1(double x, long long n)
    {
        if(n == 0) return 1;
        double ret = pow1(x, n/2);
        return (n % 2 == 0 ? ret * ret : ret * ret * x);  
    }
};

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

// 计算bool二叉树的值
class Solution6 
{
public:
    bool evaluateTree(TreeNode* root) 
    {
        if(!root->left && !root->right) return root->val;
        int left = evaluateTree(root->left);
        int right = evaluateTree(root->right);
        return root->val == 2 ? left || right : left && right;
    }
};

// 求根到叶子节点数字之和
class Solution7
{
public:
    int sumNumbers(TreeNode* root) 
    {
        return dfs(root, 0);
    }

    int dfs(TreeNode* root, int preSum)
    {
        // 1.先计算该节点的数
        preSum = preSum * 10 + root->val;
        if(!root->left && !root->right) return preSum;

        // 2.将该节点算出的数，传递给左右子树，这样左右子树才能算出叶子节点的数应该是多少
        int ret = 0;
        if(root->left) ret += dfs(root->left, preSum);
        if(root->right) ret += dfs(root->right, preSum);

        // 3.将左右子树的和计算出来，并返回
        return ret;
    }
};

// 二叉树剪枝
class Solution8
{
public:
    TreeNode* pruneTree(TreeNode* root) 
    {
        // 1.如果当前节点为空，返回nullptr
        if(!root) return nullptr;

        // 2.将左子树和右子树的所有满足要求的子树剔除
        root->left = pruneTree(root->left);
        root->right = pruneTree(root->right);
        
        // 3.如果当前节点没有子树，并且节点值为0，则返回nullptr，表示可以剔除
        if(!root->left && !root->right && root->val == 0) {
            //delete root;
            root = nullptr;
        }
        return root;
    }
};


class Solution9 
{
public:
    long prev = LONG_MIN;
    bool isValidBST(TreeNode* root) 
    {
        if(!root) return true;
        bool cond1 = isValidBST(root->left);  
        if(cond1 == false) return false; // 剪枝 
        bool cond2 = false;
        if(root->val > prev) {
            cond2 = true;
        }
        prev = root->val;
        if(cond2 == false) return false; // 剪枝
        bool cond3 = isValidBST(root->right);
        return cond1 && cond2 && cond3;
    }
};

// 二叉搜索树中第k小的节点
class Solution10
{
    int count = 0, ret = 0;
public:
    int kthSmallest(TreeNode* root, int k) 
    {
        count = k;
        dfs(root);
        return ret;
    }
    void dfs(TreeNode* root)
    {
        if(!root) return;
        dfs(root->left);
        count--;
        if(count == 0) ret = root->val;
        dfs(root->right);
    }
};

// 二叉树的所有路径
class Solution11 
{
    std::vector<std::string> ret;
public:
    std::vector<std::string> binaryTreePaths(TreeNode* root) 
    {
        dfs(root, "");
        return ret;
    }
    void dfs(TreeNode *root, std::string path)
    {
        path += std::to_string(root->val);
        if(root->left || root->right) {
            // 非叶子节点
            path += "->";
        }else { 
            // 叶子节点
            ret.emplace_back(path);
            return;
        }
        if(root->left) dfs(root->left, path);
        if(root->right) dfs(root->right, path);
    }
};

// 全排列
class Solution12 
{
    std::vector<std::vector<int>> ret;  // 记录结果
    std::vector<int> path;          // 记录当前路径
    bool check[7] = {false};        // 用来剪枝

public:
    std::vector<std::vector<int>> permute(std::vector<int>& nums) 
    {
        dfs(nums);
        return ret;
    }

    void dfs(std::vector<int>& nums)
    {
        if(nums.size() == path.size()) {
            ret.emplace_back(path);
            return;
        }

        for(int i=0; i<nums.size(); i++) {
            if(!check[i]) {
                path.emplace_back(nums[i]);
                check[i] = true;
                dfs(nums);
                path.pop_back();
                check[i] = false;
            }
        }
    }
};

// 子集
class Solution13 
{
    std::vector<std::vector<int>> ret;
    std::vector<int> path;
    bool flag = true;
public:
    void dfs(std::vector<int> &nums, int i)
    {
        if(i== nums.size()) {
            ret.emplace_back(path);
            return;
        }
        // 选
        path.emplace_back(nums[i]);
        dfs(nums, i+1);
        path.pop_back(); // 当选了这个数后，回到本层时，要将选的那个数去掉

        // 不选
        dfs(nums, i+1);// 当没有选这个数时，返回到本层时，不会对另一个选择产生影响
    }

    std::vector<std::vector<int>> subsets(std::vector<int>& nums) 
    {
        dfs(nums, 0);
        return ret;
    }
public:
    void dfs1(std::vector<int> &nums, int pos)
    {
        ret.emplace_back(path);
        for(int i=pos; i<nums.size(); i++) {
            path.emplace_back(nums[i]);
            dfs(nums, i+1);
            path.pop_back();
        }
    }

    std::vector<std::vector<int>> subsets1(std::vector<int>& nums) 
    {
        dfs(nums, 0);
        return ret;
    }
};

// 找出所有子集的异或和再求总和
class Solution14 
{
    int ret; // 计算最终结果
    int path; // 计算每个子集的异或和
public:
    void dfs(std::vector<int> &nums, int pos)
    {
        ret += path;
        for(int i=pos; i<nums.size(); i++) {
            path ^= nums[i];
            dfs(nums, i+1);
            path ^= nums[i];
        }
    }

    int subsetXORSum(std::vector<int>& nums) 
    {
        dfs(nums, 0);
        return ret;
    }
};

// 全排列2
class Solution15 
{
    std::vector<std::vector<int>> ret; // 用来统计结果
    std::vector<int> path;             // 用来记录每一个节点的数据
    bool check[9] = {false};           // 判断该数是否已经使用
public:
    void dfs(std::vector<int> &nums)
    {
        if(path.size() == nums.size()) {
            // 选完了所有的数
            ret.emplace_back(path);
            return;
        }

        for(int i=0; i<nums.size(); i++) {
            // /*&&之前表示 这个数之前没有使用过； &&后面用来确认 在同一层也没有相同的*/
            // if(!check[i] && (i == 0/*第一个数可以直接使用*/ || nums[i] != nums[i-1]/*这个数和前面不相同*/ || check[i-1]/*这个数和前面的相同，但是前面的已经在上一次用过了*/) ) {
            //     check[i] = true;
            //     path.emplace_back(nums[i]); // 选择本层的数
            //     dfs(nums);
            //     path.pop_back();
            //     check[i] = false;
            // }
            if(check[i] || (i != 0 && nums[i] == nums[i-1] && !check[i-1]) ) continue;
            check[i] = true;
            path.emplace_back(nums[i]); // 选择本层的数
            dfs(nums);
            path.pop_back();
            check[i] = false;
        }
    }

    std::vector<std::vector<int>> permuteUnique(std::vector<int>& nums) 
    {
        // 先对数组进行排序
        sort(nums.begin(), nums.end());
        dfs(nums);
        return ret;
    }
};

// 电话号码的字符组合
class Solution16 
{
    std::unordered_map<char, std::string> info;
    std::vector<std::string> args; //需要使用到的字母
    std::vector<std::string> ret;
    std::string path;
public:
    void dfs(std::vector<std::string>& args, int pos)
    {
        if(path.size() == args.size()) {
            ret.emplace_back(path);
            return;
        }

        for(int i=0; i<args[pos].size(); i++) {
            path.push_back(args[pos][i]);
            dfs(args, pos + 1);
            path.pop_back();
        }
    }

    std::vector<std::string> letterCombinations(std::string digits) 
    {
        if(digits.empty()) return ret;
        info.emplace('2', "abc");
        info.emplace('3', "def");
        info.emplace('4', "ghi");
        info.emplace('5', "jkl");
        info.emplace('6', "mno");
        info.emplace('7', "pqrs");
        info.emplace('8', "tuv");
        info.emplace('9', "wxyz");
        for(char ch : digits) {
            std::cout << ch << "->" << info[ch] << std::endl;
            args.emplace_back(info[ch]);
        }
        dfs(args, 0);
        return ret;
    }
};

// 括号生成
class Solution17 
{
    int right = 0, left = 0, num = 0;
    std::string path;
    std::vector<std::string> ret;
public:
    void dfs()
    {
        if(right == num) {
            ret.emplace_back(path);
            return;
        }

        // 如果左括号的数量大于等于num，剪枝
        if(left < num) {
            path += '('; left++;
            dfs();
            path.pop_back(); left--;
        }

        // 如果右括号的数量>=左括号，说明不合法，剪枝
        if(right < left) {
            path += ')'; right++;
            dfs();
            path.pop_back(); right--;
        }
    }

    std::vector<std::string> generateParenthesis(int n) 
    {
        num = n;
        dfs();
        return ret;
    }
};

// 组合
class Solution18 
{
    std::vector<std::vector<int>> ret;
    std::vector<int> path;
public:
    void dfs(int n, int k, int pos)
    {
        if(path.size() == k) {
            ret.emplace_back(path);
            return;
        }

        for(int i=pos; i<=n; i++) {
            path.emplace_back(i);
            dfs(n, k, i+1);
            path.pop_back();
        }
    }

    std::vector<std::vector<int>> combine(int n, int k) 
    {
        dfs(n, k, 1); 
        return ret;   
    }
};

// 目标和
class Solution19 
{
    // 使用全局变量path会超时！！！！！！！！！！！！
    int ret = 0;
    int path = 0;
    std::vector<int> tmp;   // for debug
public:
    void dfs1(std::vector<int> &nums, int target, int pos)
    {
        // 这样判断会导致提前退出
        // if(path == target)
        if(pos == nums.size()) {
            //for(int e : tmp) {
            //    std::cout << e << " ";
            //}
            //std::cout << std::endl;
            if(path == target) ret++;
            return;
        }

            // 选+号
            path += nums[pos]; 
            //tmp.emplace_back(nums[i]);
            dfs1(nums, target, pos+1);
            path -= nums[pos];
            //tmp.pop_back();

            // 选-号
            path -= nums[pos]; 
            //tmp.emplace_back(nums[i] * -1);
            dfs1(nums,target, pos+1);
            path += nums[pos];
            //tmp.pop_back();
    }

    int findTargetSumWays1(std::vector<int>& nums, int target) 
    {
        dfs1(nums, target, 0);
        return ret;
    }
public:
    void dfs2(std::vector<int> &nums, int target, int path, int pos)
    {
        // 这样判断会导致提前退出
        // if(path == target)
        if(pos == nums.size()) {
            if(path == target) ret++;
            return;
        }

        // 选+号
        dfs2(nums, target, path + nums[pos], pos+1);
        // 选-号
        dfs2(nums, target, path - nums[pos], pos+1);
    }

    int findTargetSumWays2(std::vector<int>& nums, int target) 
    {
        dfs2(nums, target, 0, 0);
        return ret;
    }
};

// 组合总和
class Solution20
{
public:
    std::vector<std::vector<int>> ret;
    std::vector<int> _path;
    void dfs1(std::vector<int> &nums, int target, int path, int pos)
    {
        if(path == target) {
            ret.emplace_back(_path);
        }
        if(path > target || pos == nums.size()) return;

        for(int i=pos; i<nums.size(); i++) {
            _path.emplace_back(nums[i]);
            dfs1(nums, target, path + nums[i], i);
            _path.pop_back();
        }
    }

    std::vector<std::vector<int>> combinationSum1(std::vector<int>& nums, int target) 
    {
        dfs1(nums, target, 0, 0);       
        return ret;
    }
public:
    std::vector<std::vector<int>> ret;
    std::vector<int> path;
    int aim;
    void dfs(std::vector<int> &nums, int pos, int sum)
    {
        if(sum == aim) {
            ret.emplace_back(path);
            return;
        }
        if(sum > aim || pos == nums.size()) return;

        // 枚举个数
        for(int k=0; k*nums[pos]+sum <= aim; k++) {
            if(k) path.emplace_back(nums[pos]);
            dfs(nums, pos+1, sum + k *nums[pos]);
        }

        // 恢复现场
        for(int k=1; k*nums[pos] + sum <= aim; k++) {
            path.pop_back();
        }
    }

    std::vector<std::vector<int>> combinationSum(std::vector<int>& nums, int target) 
    {
        aim = target;
        dfs(nums, 0, 0); 
        return ret;
    }
};

// 字母大小写全排列
class Solution21
{
    std::vector<std::string> ret;
    std::string path;
public:
    void dfs(std::string &s, int pos)
    {
        if(pos == s.size()) {
            ret.emplace_back(path);
            return;
        }

        // 不处理
        path += s[pos];
        dfs(s, pos+1);
        path.pop_back();

        // 大小写改变
        if(s[pos] >= 'a' && s[pos] <= 'z') {
            path += s[pos] - 32;
            dfs(s, pos+1);
            path.pop_back();
        }else if(s[pos] >= 'A' && s[pos] <= 'Z') {
            path += s[pos] + 32;
            dfs(s, pos+1);
            path.pop_back();
        }
    }

    std::vector<std::string> letterCasePermutation(std::string s) 
    {
        dfs(s, 0);
        return ret;
    }
};

int main()
{
    std::vector<int> a({3,2,1,0});
    std::vector<int> b;
    std::vector<int> c;
    Solution1().hanota(a, b, c);
    return 0;
}